COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	lambda[f82,jmc]		How expensive is lambda calculus computationally?
C00005 ENDMK
C⊗;
lambda[f82,jmc]		How expensive is lambda calculus computationally?

	In lambda calculus computation, the basic step is a
lambda conversion.  This can be done by substitution of the
arguments for variables, but is more usually done by extending
the environment.  There are also the lambda calculus forms of
car, cdr, cons and conditional expressions to be considered.
It would seem that each of these should be compared in essential
computational cost with the traditional LISP way of doing the
operation.  The lambda calculus interpreter must  cons  from
a free storage list, and it would a priori seem that it must
be more efficient to do the  conses  directly than to have
them occur at a lower level of interpretation.  However, we'll
see.

	Note also that each operation should be considered
separately, since it might be better to do some operations one
way and some another.

Steele and Sussman's "Art of the Interpreter" mentions

(define (cons ad) (lambda (m) (if (= m 0) a d)))

(define (car x) (x 0))

(define (cdr x) (x 1))

or alternatively

(define (cons a d) (lambda (m) (m a d)))

(define (car x) (x (lambda (a d) a)))

(define (cdr x) (x (lambda (a d) d)))

With RPLACs we have

(define (cons a d)
	(lambda (m)
		(m a d (lambda (z) (setq a z)) (lambda (z) (setq d z)))))

(define (car x)
	(x (lambda (a d sa sd) a))

(define (cdr x)
	(x (lambda (a d sa sd) d))

(define (rplaca x y)
	(x (lambda (a d sa sd)
		   (progn (sa y) x))))

(define (rplaca x y)
	(x (lambda (a d sa sd)
		   (progn (sd y) x))))